1. Field of the Invention
The present invention relates to the decoding of modulated signals. More specifically, the present invention relates to decoding trellis coded modulated data using a conventional Viterbi decoder.
2. The Background Art
FIG. 1 is a block diagram illustrating a communications system having digital signal transmission and reception. A transmission portion of the system includes an encoder 10, a puncture module 12, and a modulator 14 providing a coded modulated signal at a communication channel 16. Similarly, a reception portion of the digital signal transmission and reception system includes a demodulator 18, a depuncturing module 20, and a decoder 22.
The encoder 10 may be a convolutional encoder. Convolutional codes typically include redundant symbols to increase the effective signal to noise ratio. In this manner, the probability of errors introduced during transmission is reduced. Standard convolutional coding techniques increase required bandwidth. However, some of the coded bits may be systematically removed in favorable channel conditions through a process called puncturing.
The encoder 10 is defined by the number of coded bits per symbol (CBPS) it produces as well as by its rate, which is defined as the ratio between the number of input bits to the number of output bits. For an encoder, the rate is equal to the number of input bits to the decoder divided by the number of output bits per symbol it produces. Thus, an encoder that takes a single bit and produces two coded bits has a rate of 1/2. The ratio is read inversely for the decoder, thus a decoder with a rate of 1/2 takes two coded bits and produces a single decoded bit.
The modulated signal includes an in-phase (I) component and a quadrature (Q) component. When the modulated signal is received, after conversion from an analog to a digital signal, each bit is demodulated into the in-phase and quadrature signal components by the demodulator 18 using sine and cosine functions.
The decoder 22 is typically a Viterbi decoder. Viterbi decoders allow the system to achieve most of the coding gain promised by a particular convolutional encoder. The rate and the number of coded bits per symbol of a decoder will match that of the corresponding encoder. In order to optimally perform the decoding, most Viterbi decoders are trellis Viterbi decoders (and the matching Viterbi encoders are trellis Viterbi encoders). A trellis Viterbi decoder operates on the received in-phase (I) and quadrature (Q) signals and processes them using a trellis diagram similar to that of the convolutional encoder. FIG. 2 depicts an example trellis diagram. The trellis diagram has two states 40 and two symbol epochs. The paths from state to state are determined by the bits of the data. Thus, in FIG. 2 there are two bits in the data, evidenced by the fact that there are two parallel paths at each state transition. In general, there are 2.sup.k paths out of and into a state, where k is the number of information bits.
A trellis diagram is read from left to right. Therefore, in order to determine the a values of the data bits, the trellis Viterbi decoder attempts to determine which states have been visited. FIG. 3 depicts the trellis diagram of data after it has been passed through the Viterbi decoder, which indicates the values of the data. The complexity of using the trellis Viterbi decoder system lies in the fact that there are parallel branches at each state transition. For example, in an 8-PSK system using 2 CPBS, there will be two branches at each state transisition (like the paths in FIGS. 2-3). Both of these paths represent the coded bit and each is determined by the uncoded bit. For each additional uncoded bit which is used, the number of parallel branches doubles. This increases the complexity in the implementation of these decoders.
The existence of parallel branches means that the number of data lines within the Viterbi decoder must be at least double what it would be without parallel branches (as in a conventional Viterbi decoder). This additionally leads to an increase in the size and cost of the trellis Viterbi decoder. Furthermore, more computational ability is required to process the code. Another drawback is that the memory associated with the Viterbi decoder used in the present invention (which stores a lookup table for computational purposes) must be bigger than in a conventional Viterbi decoder.
It is therefore an object of the present invention to provide a method of transforming the incoming symbols using a lookup table to allow decoding with a conventional Viterbi decoder.
It is a further object of the present invention to provide an architecture that allows for decoding of a trellis encoded sequence without using parallel branches.
It is a further object of the present invention to provide an architecture that allows for decoding of a trellis encoded sequence without using parallel branches using a conventional Viterbi decoder.
It is a further object of the present invention to provide a method for decoding trellis encoded data which requires less memory than previously required.